package LeetCode.Recursion;

/**
 * @author : LdLtd
 * @Date : 2023/8/5
 * @Description:21. 合并两个有序链表
 */
public class merge_two_sorted_lists {

     // Definition for singly-linked list.
      public class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }
     //非递归实现  空间时间o(m+n)
     class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode res=new ListNode();
            ListNode p=res;
            while(list1!=null&&list2!=null){
                if(list1.val<list2.val){
                    res.next=list1;
                    list1=list1.next;
                    res=res.next;
                }else{
                    res.next=list2;
                    list2=list2.next;
                    res=res.next;
                }
            }
            res.next=list1==null?list2:list1;
            return p.next;
        }
    }
    /*递归实现  时间o(m+n)空间o（1）*/
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }else if(list2==null){
            return list1;
        }else if(list1.val<list2.val){
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
        }else {
            list2.next=mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}
